public class PushdownAutomata extends NondeterministicFiniteAutomata
{
	/*
	 * MEMBER VARIABLES
	 */
	
	private PushdownState[] _states;
	private PushdownState[] _activeStates;
	private String _initialStackSymbol;
	
	
	
	/*
	 * CONSTRUCTORS
	 */
	
	// This is still really hairy code.  It should REALLY be tested
	// on a more complex Pushdown Automata before being convinced
	// this code is bug free.  Also, saves don't write correctly for 
	// Pushdown Automata yet.  It's not that it's hard to fix, it's that
	// I'm tired of working on this for tonight.  
	// As is, things work right for the FA tested.  All the outputs are 
	// correct.  See FiniteAutomata main method for picture of the PDA.  
	public PushdownAutomata(String input)
	{
		super(input);
		this.fixStates();
		System.out.print(":  ");
		System.out.println(this.simulate("".split("")));
		System.out.print("0:  ");
		System.out.println(this.simulate("0".split("")));
		System.out.print("1:  ");
		System.out.println(this.simulate("1".split("")));
		System.out.print("10:  ");
		System.out.println(this.simulate("10".split("")));
		System.out.print("11:  ");
		System.out.println(this.simulate("11".split("")));
		System.out.print("100:  ");
		System.out.println(this.simulate("100".split("")));
		System.out.print("101:  ");
		System.out.println(this.simulate("101".split("")));
		System.out.print("110:  ");
		System.out.println(this.simulate("110".split("")));
		System.out.print("111:  ");
		System.out.println(this.simulate("111".split("")));
		System.out.print("1000:  ");
		System.out.println(this.simulate("1000".split("")));
		System.out.print("1001:  ");
		System.out.println(this.simulate("1001".split("")));
		System.out.print("1010:  ");
		System.out.println(this.simulate("1010".split("")));
		System.out.print("1011:  ");
		System.out.println(this.simulate("1011".split("")));
		System.out.print("1100:  ");
		System.out.println(this.simulate("1100".split("")));
		System.out.print("1101:  ");
		System.out.println(this.simulate("1101".split("")));
		System.out.print("1110:  ");
		System.out.println(this.simulate("1110".split("")));
		System.out.print("1111:  ");
		System.out.println(this.simulate("1111".split("")));
		System.out.print("10000:  ");
		System.out.println(this.simulate("10000".split("")));
		System.out.print("10001:  ");
		System.out.println(this.simulate("10001".split("")));
		System.out.print("10010:  ");
		System.out.println(this.simulate("10010".split("")));
		System.out.print("10011:  ");
		System.out.println(this.simulate("10011".split("")));
		System.out.print("10100:  ");
		System.out.println(this.simulate("10100".split("")));
		System.out.print("10101:  ");
		System.out.println(this.simulate("10101".split("")));
		System.out.print("10110:  ");
		System.out.println(this.simulate("10110".split("")));
		System.out.print("10111:  ");
		System.out.println(this.simulate("10111".split("")));
		System.out.print("11000:  ");
		System.out.println(this.simulate("11000".split("")));
		System.out.print("11001:  ");
		System.out.println(this.simulate("11001".split("")));
		System.out.print("11010:  ");
		System.out.println(this.simulate("11010".split("")));
		System.out.print("11011:  ");
		System.out.println(this.simulate("11011".split("")));
		System.out.print("11100:  ");
		System.out.println(this.simulate("11100".split("")));
		System.out.print("11101:  ");
		System.out.println(this.simulate("11101".split("")));
		System.out.print("11110:  ");
		System.out.println(this.simulate("11110".split("")));
		System.out.print("11111:  ");
		System.out.println(this.simulate("11111".split("")));
		
		System.out.print("01:  ");
		System.out.println(this.simulate("01".split("")));
		System.out.print("0011:  ");
		System.out.println(this.simulate("0011".split("")));
		System.out.print("000111:  ");
		System.out.println(this.simulate("000111".split("")));
		System.out.print("00001111:  ");
		System.out.println(this.simulate("00001111".split("")));
		System.out.print("000001111:  ");
		System.out.println(this.simulate("000001111".split("")));
	}
	
	
	
	/*
	 * CONCRETE METHODS
	 */
	
	@Override
	public boolean simulate(String[] word)
	{
		this._activeStates = new PushdownState[1];
//		if (null == this._states[0]._initialStack)
//		{
			System.out.println(this._states[0]._initialStack);
//		}
		this._activeStates[0] = new PushdownState(this._states[0], new String[] {this._states[0]._initialStack}, 0);
		this._activeStates = this.doEpsilonTransitions(this._activeStates);
		// Will hold (temporarily) all the states that become active after
		// reading the first letter.  
		PushdownState[] newActiveStates = new PushdownState[this._stateCount];
		int activeStates = 0;
		for (int i = 1; i < word.length; i++)
		{	// For each letter in the word...  
			for (PushdownState activeState : this._activeStates)
			{	// For each currently active state...  
				// Get the next states for this state, including
				// states from epsilon transitions
				Object[] nextStates1 = activeState.PAtrans(word[i]);
				PushdownState[] nextStates = new PushdownState[nextStates1.length / 3];
				for (int k = 0; k < nextStates1.length; k = k + 3)
				{
					PushdownState ps = (PushdownState)this.getStateFromName(nextStates1[k].toString());
					String[] sa = (String[])nextStates1[k + 1];
					nextStates[k / 3] = new PushdownState(ps, sa, (int)nextStates1[k+2]);
				}
				nextStates = this.doEpsilonTransitions(nextStates);
				for (PushdownState next : nextStates)
				{	// Then add only the states not already in newActiveStates
					boolean inThere = false;
					for (int k = 0; k < activeStates; k++)
					{
						if (newActiveStates[k].equals(next))
						{
							inThere = true;
						}
					}
					if (!inThere)
					{
						if (activeStates == newActiveStates.length)
						{
							newActiveStates = this.increaseBy1(newActiveStates);
						}
						newActiveStates[activeStates] = next;
						activeStates++;
					}
				}
			}
			// Clear _activeStates and add the new active states
			this._activeStates = new PushdownState[activeStates];
			for (int j = 0; j < activeStates; j++)
			{
				this._activeStates[j] = newActiveStates[j];
			}
			activeStates = 0;
			newActiveStates = new PushdownState[this._stateCount];
		}
		// Do the final epsilon transitions
		this._activeStates = this.doEpsilonTransitions(this._activeStates);
		for (PushdownState state : this._activeStates)
		{ // Check for accepting states
			if (state.getAccepting())
			{
				return true;
			}
		}
		// :-(  
		return false;	}
	
	public PushdownState[] doEpsilonTransitions(PushdownState[] states)
	{
		// newStates will store all states present in "states", as well
		// as all states that can be gotten to by epsilon transitions from
		// a state in "states".  
		PushdownState[] newStates = new PushdownState[states.length];
		for (int i = 0; i < states.length; i++)
		{
			newStates[i] = states[i];
		}
		int newCount = states.length;
		for (PushdownState pdstate : states)
		{	// For each state in states...  
			// Do an epsilon transition for that state
			Object[] newNewStates1 = pdstate.PAtrans("");
			PushdownState[] newNewStates = new PushdownState[newNewStates1.length / 3];
			for (int k = 0; k < newNewStates1.length / 3; k++)
			{
				newNewStates[k] = new PushdownState((PushdownState)this.getStateFromName((String)newNewStates1[k]), (String[])newNewStates1[k+1], (int)newNewStates1[k+2]);
			}
			boolean isIn = false;
			for (PushdownState newNewString : newNewStates)
			{	// For each of those epsilon transitions...  
				for (int k = 0; k < newCount; k++)
				{	// Check if that new state is already in newStates
					if (newStates[k].getName().equals(newNewString.getName())
						&& newStates[k].getStack().equals(newNewString.getStack()))
					{
						isIn = true;
					}
				}
				if (!isIn)
				{	// If not, put it in
					if (newCount == newStates.length)
					{
						newStates = this.increaseBy1(newStates);
					}
					newStates[newCount] = newNewString;
					newCount++;
				}
			}
		}
		if (newCount == states.length)
		{	// No new states were added, so we're done
			return states;
		}
		else
		{	// We added new states via epsilon transitions
			// So see if those new states have any epsilon transitions
			// The String[] passed to this method must have the correct size
			PushdownState[] finalStrings = new PushdownState[newCount];
			for (int j = 0; j < newCount; j++)
			{
				finalStrings[j] = newStates[j];
			}
			return doEpsilonTransitions(finalStrings);
		}
	}
	
	// Some issue with casting occurs without this I think.  
	public void fixStates()
	{
		State[] temp = this.getStates();
		PushdownState[] newArray = new PushdownState[temp.length];
		for (int i = 0; i < this._stateCount; i++)
		{
			newArray[i] = (PushdownState)temp[i];
		}
		this._states = newArray;
	}
	
	public PushdownState[] increaseBy1(PushdownState[] array)
	{
		PushdownState[] newArray = new PushdownState[array.length + 1];
		for (int i = 0; i < array.length; i++)
		{
			newArray[i] = array[i];
		}
		return newArray;
	}
	
	@Override
	public String isValid()
	{
		return "";
	}
}